348. Design Tic-Tac-Toe
Medium

Assume the following rules are for the tic-tac-toe game on an n x n board between two players:

  1. A move is guaranteed to be valid and is placed on an empty block.
  2. Once a winning condition is reached, no more moves are allowed.
  3. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Implement the TicTacToe class:

  • TicTacToe(int n) Initializes the object the size of the board n.
  • int move(int row, int col, int player) Indicates that player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move.

Follow up:
Could you do better than O(n2) per move() operation?

 

Example 1:

Input
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Output
[null, 0, 0, 0, 0, 0, 0, 1]

Explanation
TicTacToe ticTacToe = new TicTacToe(3);
Assume that player 1 is "X" and player 2 is "O" in the board.
ticTacToe.move(0, 0, 1); // return 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

ticTacToe.move(0, 2, 2); // return 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

ticTacToe.move(2, 2, 1); // return 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

ticTacToe.move(1, 1, 2); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

ticTacToe.move(2, 0, 1); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

ticTacToe.move(1, 0, 2); // return 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

ticTacToe.move(2, 1, 1); // return 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

 

Constraints:

  • 2 <= n <= 100
  • player is 1 or 2.
  • 0 <= row, col < n
  • (row, col) are unique for each different call to move.
  • At most n2 calls will be made to move.
Accepted
136,145
Submissions
242,253
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions
Show Hint 1
Could you trade extra space such that move() operation can be done in O(1)?
Show Hint 2
You need two arrays: int rows[n], int cols[n], plus two variables: diagonal, anti_diagonal.

Average Rating: 4.84 (25 votes)

Premium

Solution


Overview

Tic Tac Toe is one of the classic games most of us have played in our childhood. The game rules are pretty simple. There are 2 players that take turns marking a position on an n * n board. The first player that makes n marks horizontally, vertically, or diagonally, wins the game.

The brute force approach to solve this problem is to iterate over the entire board of size n * n and check if the current player has marked any row, column, diagonal or anti-diagonal.

This approach is exhaustive and requires O(n2)O(n^2) time for every move. Let's look at other more efficient approaches to solve the problem.


Approach 1: Optimized Brute Force

Intuition

The simplest and most intuitive approach is to check on every move if the current player has won. Each player makes a move by marking a cell on the board. The given cell is located at row row and column col. The 4 ways in which a player can win are as follows:

  • Player has marked the entire row given by row.
  • Player has marked the entire column given by col.
  • Player has marked the diagonal beginning at the top left corner of the board and ending at the bottom right corner.
  • Player has marked the anti-diagonal beginning at the top right corner of the board and ending at the bottom left corner.

The following figure illustrates the 4 winning conditions.

img

How do we identify which cells lie on the diagonal or anti-diagonal?

Every cell on the main diagonal has a unique property; the row index equals the column index. Similarly, for every cell on the anti-diagonal, the value of the column index is equal to n - row - 1.

img

Every move, we will check if any of the above conditions are true. If yes, we declare the current player as the winner and finish the game.

Algorithm

  1. For a given n, initialize a 2-dimensional array board of size n * n with the values of all elements set to 0.

  2. Every move, mark the row and col on the board with the current player's id player.

  3. Now, we will check the following conditions to see if the current player has won.

    • Check if all of the cells for the given row are marked by the current player. To do so, we must iterate over all the columns ranging from index 0 to n - 1, keeping the row index constant.

    • Check if all of the positions for the given col are marked by the current player. To do so, we must iterate over all the rows ranging from index 0 to n - 1, keeping the col index constant.

    • Check if the main diagonal is completely marked by the current player.

      From the above intuition, we know that for each cell on the main diagonal, the row and col indices are equal. Thus, every cell on the diagonal can be given by board[row][row].

    • Check if the anti-diagonal is completely marked by the current player.

      From the above intuition for each cell in the anti-diagonal, the value of the col index is equal to n - row - 1. Thus, every cell in the anti-diagonal could be given by board[row][n - row - 1].

  4. If the current player wins the game, then return player. Otherwise, return 0 indicating that no one has won the game.

Implementation

Complexity Analysis

  • Time Complexity: O(n)O(n), as for every move we are iterating over n cells 44 times to check for each of the column, row, diagonal row, and anti-diagonal. This gives us time complexity of O(4n)O(4 \cdot n) which is equivalent to O(n)O(n).

  • Space Complexity: O(n2)O(n^2), as we are using 2-dimensional array board of size n * n.


Approach 2: Optimised Approach

Intuition

Our goal is to find if a player has won by marking an entire row, column, diagonal, or anti diagonal cells. Can we find this in constant time without iterating over each of the horizontal, vertical, and diagonal rows on every move? Yes! Let's find out how.

Let's break the problem into 2 parts,

  • First, on every move, we must determine whether a player has marked all of the cells in a row or column. In other words, we could say that, if there are n rows and n columns on a board, the player must have marked a certain row or column n times.

    From the given conditions, we know that a move is always valid and placed on an empty cell. Hence, we can be certain that if a player has marked any row n times, they must have marked a different column each time.

  • Second, on every move, we must determine whether a player has marked all of the cells on the main diagonal or anti-diagonal. Irrespective of the size of the board, there can only be one diagonal and one anti-diagonal.

    Also, there are always n cells on the diagonal or anti-diagonal. Thus, to win by either of these, a player must have marked the cells on the diagonal or anti-diagonal n times.

Let's understand how can we implement this approach.

Algorithm

From the above intuition, we understand that we must use a data structure to count how many times a player has marked a particular row, column, or diagonal.

  • To implement the first part, for each player, we will build an array rows of size n, where rows[i] stores the number of times a player has marked a cell on the ithi^{th} row. Likewise, for each player, we will also build an array cols of size n.

    Winning Condition: The player will win if either rows[i] or cols[j] is equal to n after the player has marked the cell on the ithi^{th} row and jthj^{th} column.

    Let player1Rows and player1Cols be the rows and cols array for player 1. Likewise, let player2Rows and player2Cols be the rows and cols for player 2. The following figure illustrates the process for move(0, 0, 1) and move(0, 2, 2).

img

  • To implement the second part, we can use a similar idea as above. Since there is only one diagonal and one anti-diagonal, for each player, we only need 2 integer variables diagonal and antiDiagonal. These variables will store how many times a cell has been marked on each of the diagonals.

    Winning Condition: After a player has marked a cell on a diagonal row, we check if the value of variable diagonal for that player is equal to n. Similarly, after a player has marked a cell on an anti-diagonal row, we check if the value of variable antiDiagonal for that player is equal to n.

    Let player1Diagonal and player1AntiDiagonal be the diagonal and antiDiagonal variables for player 1. Likewise, let player2Diagonal and player2AntiDiagonal be the diagonal and antiDiagonal for player 2. The following figure illustrates the process for move(1, 1, 1) and move(2, 0, 2).

img

Question - Can we further optimize this algorithm?"

Yes, we can. Since there are only 2 players, when implementing part 1, we can use the same data structure to store the marked row and column values for both players.

One way to implement this is to increment the count when player 1 marks a cell and decrement the count when player 2 marks a cell. With this, we can say that, if the value of rows[i] is equal to n, player 1 has marked ithi^{th} row n times. Similarly, if the value of rows[i] is equal to -n, then player 2 has marked the ithi^{th} row n times.

Similar logic applies to the columns and diagonals.

The following animation illustrates the idea.

Current
1 / 8

The algorithm can be implemented as follows:

  1. For a given n, initialize arrays rows and cols of size n with the value of every element set to 0.

  2. For each move, we must increment/decrement the row, column, diagonal, and anti-diagonal according to who is the current player and which cell was marked. If the current player is player 1, we increment the value and if it is player 2, we decrement the value.

    Note: If we apply simple math rules, we can increment or decrement the values irrespective of the player.

    We can use an additional variable currentPlayer with the value 1 for player 1 and -1 for player 2, and add the value of currentPlayer to the current row, column, diagonal and anti-diagonal.

  3. As a final step, we must determine whether the current player has won the game. If any row, column, diagonal, or anti-diagonal is equal to n (for player 1) or -n (for player 2) then the current player has won the game.

    Also, rather than having separate conditions to check whose turn it is, we can check the absolute values.

Implementation

Complexity Analysis

Let, nn be the length of string ss.

  • Time Complexity: O(1)O(1) because for every move, we mark a particular row, column, diagonal, and anti-diagonal in constant time.

  • Space Complexity: O(n)O(n) because we use arrays rows and cols of size n. The variables diagonal and antiDiagonal use constant extra space.

Report Article Issue

Comments: 10
pseudohuman's avatar
Read More

Amazing solution. Approach 2 was literally an eye-opener.
It shows how the given constraints play equally important role in solving a problem. You were able to relax this problem using those constraints and solve it in constant time. Thanks for the article!

4
Reply
Share
Report
ZijiaqiXu's avatar
Read More

Well, my first idea is close to the 2nd approach except that I used 2 arrays of rows/cols/diags, each counts the number of moves made by each player, which took 2 times of space but is a little bit faster.

3
Reply
Share
Report
L3S's avatar
Read More

In case someone interested in python3

class TicTacToe:
    def __init__(self, n: int):
        self.n=n
        self.horiz=[0]*n
        self.vert=[0]*n
        self.diag1=0
        self.diag2=0

    def move(self, row: int, col: int, player: int) -> int:
        n=self.n
        move=1
        if player == 2:
            move=-1
        
        self.horiz[col] += move
        self.vert[row] += move
        
        if row==col: 
            self.diag1 += move
        if row+col == (n-1):
            self.diag2 += move
            
        if abs(self.horiz[col])==n or abs(self.vert[row])==n or abs(self.diag1)==n or abs(self.diag2)==n:
            return player
        return 0

1
Reply
Share
Report
abhi_1729's avatar
Read More

I dont know if I thought of 2nd approach because the follow up said i could do better than O(n^2), or if that was the natural thing to do

0
Reply
Share
Report
Yedelm's avatar
Read More

For the O(1) solution, my initial thought is using HashMap for rows and columns...
Using the two arrays in Approach2 is so clever which is a good trick to remember :)

0
Reply
Share
Report
jwalahe's avatar
Read More

The second approach is goddamn amazing. Thank you for brilliant explanation. :)

0
Reply
Share
Report
yuchen29's avatar
Read More

The 2nd approach is amazing! My brain won't come up with such a solution ever...

0
Reply
Share
Report
JinZhenlin's avatar
Read More

This is an award winning article! Thank you for sharing the explanation!

0
Reply
Share
Report
anineela's avatar
Read More

This is truly an EXCELLENT article. Approach two blew my mind.

0
Reply
Share
Report
ltrager's avatar
Read More

The second solution is interesting but I question how practical it would be. Part of playing a game is seeing the board. You can't print out the current state of the board with the second solution, you only know if there is a winner.

-1
Show 2 replies
Reply
Share
Report

You don't have any submissions yet.

348/1883
Contribute
|||
Saved
#301 Remove Invalid Parentheses
Hard
#302 Smallest Rectangle Enclosing Black Pixels
Hard
#303 Range Sum Query - Immutable
Easy
#304 Range Sum Query 2D - Immutable
Medium
#305 Number of Islands II
Hard
#306 Additive Number
Medium
#307 Range Sum Query - Mutable
Medium
#308 Range Sum Query 2D - Mutable
Hard
#309 Best Time to Buy and Sell Stock with Cooldown
Medium
#310 Minimum Height Trees
Medium
#311 Sparse Matrix Multiplication
Medium
#312 Burst Balloons
Hard
#313 Super Ugly Number
Medium
#314 Binary Tree Vertical Order Traversal
Medium
#315 Count of Smaller Numbers After Self
Hard
#316 Remove Duplicate Letters
Medium
#317 Shortest Distance from All Buildings
Hard
#318 Maximum Product of Word Lengths
Medium
#319 Bulb Switcher
Medium
#320 Generalized Abbreviation
Medium
#321 Create Maximum Number
Hard
#322 Coin Change
Medium
#323 Number of Connected Components in an Undirected Graph
Medium
#324 Wiggle Sort II
Medium
#325 Maximum Size Subarray Sum Equals k
Medium
#326 Power of Three
Easy
#327 Count of Range Sum
Hard
#328 Odd Even Linked List
Medium
#329 Longest Increasing Path in a Matrix
Hard
#330 Patching Array
Hard
#331 Verify Preorder Serialization of a Binary Tree
Medium
#332 Reconstruct Itinerary
Medium
#333 Largest BST Subtree
Medium
#334 Increasing Triplet Subsequence
Medium
#335 Self Crossing
Hard
#336 Palindrome Pairs
Hard
#337 House Robber III
Medium
#338 Counting Bits
Easy
#339 Nested List Weight Sum
Medium
#340 Longest Substring with At Most K Distinct Characters
Medium
#341 Flatten Nested List Iterator
Medium
#342 Power of Four
Easy
#343 Integer Break
Medium
#344 Reverse String
Easy
#345 Reverse Vowels of a String
Easy
#346 Moving Average from Data Stream
Easy
#347 Top K Frequent Elements
Medium
#348 Design Tic-Tac-Toe
Medium
#349 Intersection of Two Arrays
Easy
#350 Intersection of Two Arrays II
Easy